package sort;
/*
* 统计数组中的 逆序对
*      归并排序:拆分合并,使用到一个辅助数组
* */
public class Offer51ReversePairs {
    int count=0;
    public int reversePairs(int[] nums) {
        sort(nums,0,nums.length-1,new int[nums.length]);
        return count;
    }

    private void sort(int[] nums, int left, int right, int[] tmp) {
        if(left<right){
            int mid=(left+right)/2;
            sort(nums, left, mid, tmp);
            sort(nums, mid+1, right, tmp);
            merge(nums,left,mid,right,tmp);
        }

    }

    private void merge(int[] nums, int left, int mid, int right, int[] tmp) {
        int i=left;
        int j=mid+1;
        int k=0;
        while(i<=mid && j<=right){
            if(nums[i]<=nums[j]){
                tmp[k++]=nums[i++];
            }else {
                tmp[k++]=nums[j++];
                count+=mid-i+1;
            }
        }
        while (i<=mid){
            tmp[k++]=nums[i++];
        }
        while (j<=right){
            tmp[k++]=nums[j++];
        }
        // 每次 合并时tmp数组并不是都没占完，只占right-left这么大的地方， 只起到一个辅助存储的作用
        // 只是在最后一次合并时才会将数组占用完。
        k=0;
        while (left<=right){
            nums[left++]=tmp[k++];
        }
    }
}
